package cn.edu.jxau.test;

import java.util.LinkedList;

public class Main {

    public static void main(String[] args) {
        
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        stack.push(5);
        System.out.println(stack);
        reverse(stack);
        System.out.println(stack);
    }
    
    private static <T> T getAndRemoveLastElement(Stack<T> stack) {
        
        T element = stack.pop();
        if(stack.isEmpty()) { //element是stack中的最后一个元素
            return element;
        } else {
            T lastElement = getAndRemoveLastElement(stack);
            stack.push(element);
            return lastElement;
        }
    }
    
    private static <T> void reverse(Stack<T> stack) {
        
        if(stack.isEmpty()) {
            return ;
        }
        T element = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(element);
    }
}

/**
 * 包装{@code LinkedList}，使其仅暴露堆栈相关的方法
 * @author 付大石
 */
class Stack<T> {
    
    private LinkedList<T> list;
    
    public Stack() {
        list = new LinkedList<>();
    }
    
    public void push(T item) {
        list.push(item);
    }
    
    public T pop() {
        return list.pop();
    }
    
    public T peek() {
        return list.peek();
    }
    
    public boolean isEmpty() {
        return list.isEmpty();
    }
    
    @Override
    public String toString() {
        return list.toString();
    }
}

